The invention relates to the field of the processing of digital image data from a set representative of a three-dimensional (3D) image, for simulating the deformable behavior of an object.
The invention applies more particularly, but nonexclusively, to the processing of a set of image data from a so-called medical image.
In numerous fields, it is very beneficial to be able to simulate interventions by an operator, with the aid of one or more known tools, on one or more deformable objects. Here, the term intervention is understood to mean either a manipulation, with a view for example to a displacement, or a local transformation, such as for example, in the case of a surgical intervention, incision or extraction of a part of an organ.
Simulation consists in displaying the image of an object and possibly of the region in which it customarily lies, and the representation of one tool at least whose  less than  less than virtual greater than  greater than  (in this document, words which appear within double-arrowhead brackets reflect the fact that a concept, in the context of this document, is designated with such words) displacement, relative to the object, is defined by a user interface of which a harness is maneuvered by an operator, with a view to simulating the handling of the said tool. In order to be able to simulate the reaction of the object on the tool, the user interface is capable of generating a force feedback, in accordance with the reactions of the tool. The term reaction force of an object is understood to mean force feedback.
In known devices, a reaction module makes it possible to determine this reaction force of the object on the basis of an estimated deformation of this object. This deformation is obtained with the aid of an internal forces module and of an image refresh module. The internal forces module is capable, on designation of a 3D. object appearing in a set of image data, of establishing a field of internal forces, which is representative of the deformation of the object, between nodes of a volume meshing dependent on a surface meshing of this object, on the basis of a deformation law and of an action defined by the user interface and representative of a maneuver of the tool.
The refresh module then makes it possible to calculate new image data of the object, in the presence of the estimated deformations supplemented with the representation of the tool. These new image data which form the new image of the object and possibly that of the region which surrounds it, are then displayed on a display device so that the operator can see in real time the result of the manipulation of the harness which simulates the action on the tool.
Such a device must allow the training of an operator or else the tailoring of new techniques of intervention on the object. In a field such as surgery, and more particularly still in the field of laparoscopic surgery, this type of device may make it possible to save human lives. To do this, it is imperative that the simulation makes it possible to reproduce the operator""s gesture (or in other words his action on a tool, here virtual) as faithfully as possible. This requires real-time processing of the image data, coupled with reconstruction of the forces induced by the object in response to the deformation generated by the  less than  less than tool greater than  greater than .
Now, on account of the calculation techniques used by known devices, estimation of the internal forces requires considerable calculation times which are incompatible with continuous dynamic simulation. In other words, contemporary devices do not make it possible to display, in a manner which is continuous in respect of a human eye, the entire action of a tool on a deformable object.
Moreover, no contemporary device makes it possible to simulate in real time an action such as incision, or tearing, or the removal of material from a deformable object.
The aim of the present invention is therefore to solve all or some of the aforesaid drawbacks in the field of the processing of digital image data of a 3D object.
It therefore proposes an electronic device for processing image data of the type described in the introduction, in which, on the one hand, there is provision for a  less than  less than collision greater than  greater than  module capable of estimating a point of intersection between a straight line embodying a displacement derived from the defined action and the surface meshing, and on the other hand, the internal forces module is devised so as to estimate the internal force exerted on each node of a first part at least of the volume meshing of the object on the basis of the displacement derived from the action, and applied to the nodes belonging to the surface mesh cell containing the point of intersection, of boundary conditions, and of node tensors and link tensors emanating respectively for each node and each link of at least the first part at least, from stiffness matrices specific to each volume mesh cell of at least the first part and dependent on the deformation law.
Of course, the first part of the volume mesh cell to which the above technique is applied, which will subsequently be referred to as  less than  less than masses/tensors greater than  greater than , can be equal to the complete volume mesh cell. In the contrary case (when dealing in fact with a part of this volume mesh cell), the internal forces applied to the nodes of the part complementary to this first part (referred to for example as the second part) are determined on the basis of another technique, such as for example that of finite elements relying on precalculations which are stored so as to allow real-time calculations. Such a technique is taught in particular in the article by S. Cotin, H. Delingette, M. Bro-Nielsen and N. Ayache,  less than  less than Geometric and physical representations for a simulator of hepatic surgery greater than  greater than , published in the proceedings of the conference Medicine meets with virtual reality, January 1996. In what follows, the dual technique of calculating internal forces and the deformation of the object will be referred to as a hybrid model.
This so-called masses/tensors technique used for calculating the internal forces and the deformation of the volume mesh cell of the object permits continuous simulation of an action exerted on a virtual tool at least. It is clear that the smaller the dimension of the first part of the volume mesh cell, the less will be the calculation time.
According to another characteristic of the invention, the device can comprise a meshing module allowing it to designate the 3D object(s) on which the simulation is to be performed by determination of an external envelope, then to decompose this or these envelopes into surface mesh cells, preferably of triangular form, and lastly to decompose the internal volume of each envelope into volume mesh cells on the basis of the corresponding surface meshing so as to provide the volume meshing of the associated object. It is clear that in the preferred case of a triangular surface meshing the volume mesh cells will be tetrahedral in shape. These shapes are currently preferred since they allow accurate modeling of an object of complex shape. However, of course, other types of meshing may be used.
Such external envelopes and volume mesh cells may be obtained by methods of segmentation (for example by extracting iso-surfaces) and of the Delaunay-Voronoxc3xaf type respectively. All these methods are well known to the person skilled in the art.
In one embodiment of the device, its internal forces module is capable itself of calculating the stiffness matrices of each volume mesh cell, as well as the node tensors and link tensors.
These calculations are, as was stated earlier, performed on the basis of a deformation law which is preferably of volume linear elastic type. In other words, the force exerted on a node depends on the displacements respectively of this node and of the nodes to which it is connected, relative to their respective positions of equilibrium. Of course, other more complex deformation laws could be used, in particular non-linear laws.
The internal forces module could also be devised so as to determine the internal forces exerted on some at least of the nodes of the first part of the volume meshing on the basis of the deformation law and of auxiliary surface forces dependent on stored, chosen parameters of the object, such as for example the texture of the object, the presence of structures and underlying substructures, etc.
Here, the term auxiliary surface forces should be understood to mean for example surface tensions which, in certain situations such as an incision, will make it possible to amplify a visual effect at display level.
Likewise, the internal forces module may be devised so as to estimate the displacements of the nodes of the volume meshing (at least its first part) on the basis of the displacement derived from the defined action and from external forces, in particular of gravitational force type and/or forces of interaction between objects of one and the same region. This makes it possible to take into account, on the one hand, the partial sagging of an object under its own weight, and on the other hand the presence of neighboring objects and of the ties which exist with these neighboring objects.
Preferably, the estimated displacements of the nodes, other than those of the said surface mesh cell comprising the said point of intersection, are calculated on the basis of the internal forces by successive integrations with the aid of a method chosen from among at least the Euler method and the Runge-Kutta method, and more preferably still by the so-called  less than  less than order 4 greater than  greater than  Runge-Kutta method. Of course, other methods of integration may be envisaged.
According to yet another characteristic of the invention, the internal forces module may be capable of simulating deformations not only of geometrical type, but also of incision and/or removal of material and/or tearing type.
To allow the simulation of cutting (or incision) and/or of tearing (or fracture), the internal forces module is able, after determining the estimated displacements of the nodes, to delete at least one link between neighboring nodes as a function of a first criterion, then to update the node tensors and the link tensors as a function of the deleted link(s), and lastly to recalculate the internal forces of the nodes of at least the first part of the volume meshing.
Preferably, the first criterion pertains to at least one parameter chosen from among at least one cue transmitted by the user interface and relating to the type of tool maneuvered, a volume variation of the volume mesh cell comprising the link to be deleted, and a length variation of a link of the volume mesh cell comprising the link to be deleted.
Here, the term cue is understood to mean for example an item of data specifying that the tool is maneuvered with a view to an incision or a destruction of material.
Likewise, to allow the simulation of the removal of material, the internal forces module is able, after determining the estimated displacements of the nodes, to delete a node in the event of detecting the deletion of all the links which join the said node to the neighboring nodes or as a function of the first criterion, then to update the node tensors and the link tensors as a function of the node and of the deleted links, and lastly to recalculate the internal forces of the nodes of at least the first part of the volume meshing.
The tools (here virtual) capable of cutting (or of incising) and/or of removing material are for example scalpels, cutting forceps, or else mechanical or electrical bistoury, or alternatively lasers.
Moreover, the internal forces module is preferably devised so as, in the event of the deletion of a link and/or of a node and before updating the link tensors and node tensors, to add new mutually independent nodes and new links in such a way as to locally remesh the volume meshing subsequent to the deletion.
When the device is devised so as to work according to the aforesaid hybrid model, its internal forces module is capable of determining the internal forces exerted on the nodes of at least a second part of the volume meshing on the basis of boundary conditions defined by so-called connection nodes placed at the interface between the first and second parts, and of a table of deformation tensors, each tensor of which is representative of the influence of an elementary displacement of each node of at least the second part on each other node of at least this second part.
The boundary conditions serving in the calculation of the internal forces of the second part are preferably defined by the internal forces calculated for the connection nodes when calculating the internal forces of the nodes of the first part.
In the hybrid model, the internal forces module preferably proceeds by successive iterations until a position of so-called  less than  less than equilibrium greater than  greater than  of the internal forces of the connection nodes is obtained. To do this, this module is devised so as to deduce from the values of the internal forces exerted on the nodes of the second part of the volume meshing, values of displacement of the connection nodes in such a way as to provide boundary conditions which in turn make it possible to calculate the internal forces of the nodes of the first part.
The subdivision of the volume meshing into parts (at least two) is determined on the basis of a predetermined criterion pertaining at least to a parameter of the image data of the object chosen from among physical parameters and anatomical parameters, in particular to an intensity. This subdivision can be performed during the formation of the volume meshing of the 3D object. Accordingly, when the device does not comprise a meshing module, the subdivision can be performed by an external processing. The device can comprise a partitioning module, for example forming part of the meshing module if the latter exists, intended to provide the subdivision of the volume meshing.
Preferably, the  less than  less than collision greater than  greater than  determination module is devised so as to determine a collision between at least two tools managed by the user interface. This makes it possible to manage conflicts when one or more operators maneuver at least two tools at the same time.
For this purpose, each tool is represented by at least one point embodying its end interacting with the object, and a multiplicity of points joined to one another as well as to the end, by segments, embodying its  less than  less than shank greater than  greater than .
Preferably, the collision determination module estimates the coordinates of the point of intersection between the  less than  less than tool greater than  greater than  and a surface mesh cell as follows:
Firstly, it creates a three-dimensional space encompassing the external envelope of the object, then it decomposes this space into volume blocks, the number of which is chosen so that each block comprises a number of node of the volume meshing of the object substantially equal to the number of nodes contained in the other volume blocks, each block intersecting the external surface comprising at least one node, and lastly it stores in multiplets the coordinates of each node with reference to the volume block which encompasses it. The presence of a point of the tool in the space is then effected, preferably, through a comparison between the multiplets and the coordinates of the point. One of these multiplets makes it possible to designate the volume block of the space in which the point lies.
Then, preferably, the collision detection module determines the (Euclidean) distance which separates the point of the tool from the node(s) encompassed in the designated volume block so as to determine the smallest of these distances, termed the minimum distance. Thereafter it determines the distance (for example Euclidean) which separates the point from the node(s) encompassed in a predetermined number of volume blocks neighboring the volume block in which it lies so as to compare its distances with the minimum distance. Then, it determines the collection of surface mesh cells adjacent to the node associated with the minimum distance so as to determine whether a segment defined by the position of the point of the tool and by its previous position intersects one at least of these adjacent surface mesh cells. Lastly, from this it deduces the (barycentric) coordinates of the point of intersection (or of collision) between the object and the tool, with a view to their transmission to the internal forces module.
Preferably, the collision detection module is capable of modifying the contents of the multiplets between two determinations of presence of points of the tool inside the volume blocks, in the event of detection of a deformation of the mesh by the internal forces module. This makes it possible to improve the accuracy of collision detection and hence of the calculation of the deformation.
In order to allow the most realistic possible simulation of action on one or more tools, the user interface comprises a harness maneuverable by at least one operator hand so as to simulate the maneuvering of each tool. The operator thus maneuvers the harness, which may be a  less than  less than joystick greater than  greater than  possibly fitted with actuator(s) or else an articulated  less than  less than glove greater than  greater than  fixed on his hand, then the user interface defines the displacement of the associated virtual tool on the basis of this maneuver.
According to yet another characteristic of the invention, the device comprises display means making it possible to display in real time (and continuously) the image (formed from the image data) of the object and of a representation of the tool.
The invention applies most particularly to the sets of image data representing a three-dimensional digital image of a region comprising at least one 3D object, including the designated object, and more particularly still to the sets of image data representing a three-dimensional digital image of a region of a living being (animal or human) comprising deformable anatomical structures such as the liver, the kidney, the gall bladder, or alternatively the heart.
The invention also proposes a process for processing the digital image data for implementing the device described above, comprising the following known steps:
provide a user interface capable of generating a force feedback, in accordance with the reactions of a tool,
establish, on the basis of a deformation law and of an action defined by the user interface and representative of a maneuver of the tool, a field of internal forces between nodes of a volume meshing dependent on a surface meshing of a 3D object appearing in a set of image data,
determine the reaction force of the object which corresponds to its deformation estimated on the basis of the internal forces, so that the force generated by the user interface is substantially balanced by this reaction force,
calculate new image data of the object, in the presence of the estimated deformations supplemented with the representation of the said tool,
and characterized in that there is provision for a step in which a point of intersection between a straight line embodying a displacement derived from the defined action and the surface meshing is estimated, and in that the internal force exerted on the nodes of a first part at least of the volume meshing of the object is estimated, on the basis of the displacement applied to the nodes belonging to the surface mesh cell containing the point of intersection, of boundary conditions, and of node tensors and link tensors emanating respectively for each node and each link of this part at least, from stiffness matrices specific to each volume mesh cell of at least the first part and dependent on the deformation law.